#include "util.hpp"

/**
 * author: pangchao
 * date: 2025-05-28
 * 
*/

// 写这个类是因为 gmp 提供的大数用起来实在太逆天的
// 明明简单的代码会被搞得非常臃肿
// 快是真的快 但是真的难用 不如自己封装一个
class BigInt
{
public:
    BigInt(long long data = 0)
    {
        mpz_init_set_ui(data_, data);
    }
    ~BigInt()
    {
        mpz_init_set_d(data_, 0);
        mpz_clear(data_);
    }
    BigInt(const BigInt &bigInt)
    {
        mpz_init_set(data_, bigInt.data_);
    }
    BigInt operator+(BigInt bigInt)
    {
        BigInt result(*this);
        mpz_add(result.data_, result.data_, bigInt.data_);
        return result;
    }
    BigInt operator-(BigInt bigInt)
    {
        BigInt result(*this);
        mpz_sub(result.data_, result.data_, bigInt.data_);
        return result;
    }
    BigInt operator-(BigInt bigInt) const
    {
        BigInt result(*this);
        mpz_sub(result.data_, result.data_, bigInt.data_);
        return result;
    }
    BigInt operator*(BigInt bigInt)
    {
        BigInt result(*this);
        mpz_mul(result.data_, result.data_, bigInt.data_);
        return result;
    }
    BigInt operator*(BigInt bigInt) const
    {
        BigInt result(*this);
        mpz_mul(result.data_, result.data_, bigInt.data_);
        return result;
    }
    BigInt operator/(BigInt bigInt)
    {
        BigInt result(*this);
        mpz_div(result.data_, result.data_, bigInt.data_);
        return result;
    }
    BigInt pow(BigInt bigInt)
    {
        BigInt result;
        mpz_pow_ui(result.data_, data_, mpz_get_ui(bigInt.data_));
        return result;
    }
    BigInt pow(BigInt bigInt) const
    {
        BigInt result;
        mpz_pow_ui(result.data_, data_, mpz_get_ui(bigInt.data_));
        return result;
    }
    friend std::ostream &operator<<(std::ostream &out, const BigInt &bigInt)
    {
        gmp_printf("%Zd", bigInt.data_);
        return out;
    }

    bool operator==(const BigInt& bigInt)
    {
        return (mpz_cmp(data_, bigInt.data_) == 0);
    }
    bool operator==(const BigInt& bigInt) const
    {
        return (mpz_cmp(data_, bigInt.data_) == 0);
    }
    bool operator!=(BigInt bigInt)
    {
        return !(*this == bigInt);
    }
    bool operator<(BigInt bigInt)
    {
        return (mpz_cmp(data_, bigInt.data_) < 0);
    }

    bool operator>(BigInt bigInt) const
    {
        return (mpz_cmp(data_, bigInt.data_) > 0);
    }
    bool operator<(BigInt bigInt) const
    {
        return (mpz_cmp(data_, bigInt.data_) < 0);
    }

    bool operator>(BigInt bigInt)
    {
        return (mpz_cmp(data_, bigInt.data_) > 0);
    }
    BigInt operator%(BigInt bigInt)
    {
        BigInt result;
        mpz_mod(result.data_, data_, bigInt.data_);
        return result;
    }
    BigInt& operator+=(BigInt bigInt)
    {
        mpz_add(data_, data_, bigInt.data_);
        return *this;
    }
    BigInt& operator/=(BigInt bigInt)
    {
        mpz_div(data_, data_, bigInt.data_);
        return *this;
    }
    BigInt& operator*=(BigInt bigInt)
    {
        mpz_mul(data_, data_, bigInt.data_);
        return *this;
    }
    BigInt& operator-=(BigInt bigInt)
    {
        mpz_sub(data_, data_, bigInt.data_);
        return *this;
    }
    // 前置++
    BigInt& operator++()
    {
        this->operator+=(1);
        return *this;
    }
    BigInt operator++(int)
    {
        BigInt result(*this);
        this->operator+=(1);
        return result;
    }
    // a的n次方 mod p 这里不写引用是为了可以传入常数
    // 这样做可以减少代码量 但效率会有所损失 在这里我们不需要考虑这个问题
    BigInt powm(BigInt n, BigInt p)
    {
        BigInt result;
        mpz_powm(result.data_, data_, n.data_, p.data_);
        return result;
    }

    BigInt legendre(BigInt n, BigInt p)
    {
        return n.powm((p - 1) / 2, p);
    }
    // 计算模平方根
    BigInt tonelli(BigInt n, BigInt p)
    {
        BigInt q = p - 1;
        BigInt s = 0;
        while (q % 2 == 0)
        {
            q /= 2;
            s += 1;
        }
        if (s == 1)
            return n.powm((p + 1) / 4, p);
        BigInt flag = 0;
        for (BigInt i = 2; i < p; i++)
        {
            if (p - 1 == legendre(i, p))
            {
                flag = i;
                break;
            }
        }
        BigInt c = flag.powm(q, p);
        BigInt r = n.powm((q + 1) / 2, p);
        BigInt t = n.powm(q, p);
        BigInt m = s;
        BigInt t2 = 0;
        while ((t - 1) % p != 0)
        {
            t2 = (t * t) % p;
            BigInt flag2 = 0;
            for (BigInt i = 1; i < m; i++)
            {
                if ((t2 - 1) % p == 0)
                {
                    flag2 = i;
                    break;
                }
                t2 = (t2 * t2) % p;
            }
            BigInt tmp = 2;
            tmp = tmp.pow(m - flag2 - 1);
            BigInt b = c.powm(tmp, p);
            r = (r * b) % p;
            c = (b * b) % p;
            t = (t * c) % p;
            m = flag2;
        }
        return r;
    }
    void SetBigInt(const char* numStr, const int mode)
    {
        mpz_set_str(data_, numStr, mode);
    }
    int ToInt()
    {
        return mpz_get_d(data_);
    }

public:
    static BigInt GetRandomBigInt(const int len)
    {
        clock_t time = clock();
        gmp_randstate_t grt;
        gmp_randinit_default(grt);
        gmp_randseed_ui(grt, time);
        BigInt result;
        mpz_urandomb(result.data_, grt, len);
        return result;
    }
    static BigInt GetRandomPrimeBigInt(const int len)
    {
        clock_t time = clock();
        gmp_randstate_t grt;
        gmp_randinit_default(grt);
        gmp_randseed_ui(grt, time);
        BigInt result;
        mpz_urandomb(result.data_, grt, len);
        mpz_nextprime(result.data_, result.data_);
        return result;
    }
private:
    mpz_t data_;
};